/**
 * http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/
 * 
 */

/**
 * @author michaelyi
 *
 */

package algorithm;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class WordsExtractor {

	static Set<String> dictionary;

	static {
		dictionary = new HashSet<String>();
		dictionary.add("micro");
		dictionary.add("microsoft");
		dictionary.add("soft");
		dictionary.add("software");
		dictionary.add("so");
		dictionary.add("office");
		dictionary.add("off");
		dictionary.add("of");
		dictionary.add("ice");
		// dictionary.add("microsoftoffice");
		dictionary.add("a");
		dictionary.add("aa");
		dictionary.add("aaa");
		dictionary.add("aaaa");
	}

	public WordsExtractor() {
		// TODO Auto-generated constructor stub
	}

	// brute force
	String SegmentString(String input) {
		int len = input.length();
		for (int i = 1; i < len; i++) {
			String prefix = input.substring(0, i);
			if (dictionary.contains(prefix)) {
				String suffix = input.substring(i, len);
				if (dictionary.contains(suffix)) {
					return prefix + " " + suffix;
				}
			}
		}
		return null;
	}

	/*
	 * DP: dpRec[strlen(str)] dpRec[i]: if true, previous character can split to
	 * words 
	 * for (int i = 0; i < strLen; i++) 
	 * 	 for (int j = i; j >=0 && !dpRec[i]; j--) 
	 *     dpRec[i] = true if dpRec[j] && isWord(str[j..i])
	 * 
	 * 就是一个DP
	 * f(i) = exist k > i such that word(i, k) is in dictionary && f(k) is true
	 */
	String SegmentStringIterativeDP(String input) {
		assert (input != null);

		if (input.length() == 0)
			return input;
		int[] backtrack = new int[input.length() + 1];// the words ending with
														// previous char can be
														// split into words
		for (int i = 1; i < backtrack.length; ++i) {
			backtrack[i] = -1;
		}
		for (int i = 1; i < backtrack.length; ++i) {
			for (int j = i; j >= 0; --j) {
				if (backtrack[j] >= 0
						&& dictionary.contains(input.substring(j, i))) {
					backtrack[i] = j;
					break;
				}
			}
		}

		Stack<String> stack = new Stack<String>();
		backtrack[0] = -1;
		int i = backtrack.length - 1;
		while (backtrack[i] >= 0) {
			stack.push(input.substring(backtrack[i], i));
			i = backtrack[i];
		}

		StringBuilder sb = new StringBuilder();
		while (!stack.isEmpty()) {
			sb.append(stack.pop()).append(" ");
		}

		return sb.toString();
	}

	String SegmentStringRecusiveDP(String input, Map<String, String> memoized) {
		if (dictionary.contains(input))
			return input;
		if (memoized.containsKey(input)) {
			System.out.printf("%s : memoized\n", input);
			return memoized.get(input);
		}

		int len = input.length();
		for (int i = 1; i < len; ++i) {
			String prefix = input.substring(0, i);
			if (dictionary.contains(prefix)) {
				String suffix = input.substring(i, len);
				String segSuffix = SegmentStringRecusiveDP(suffix, memoized);
				if (segSuffix != null) {
					String str = prefix + " " + segSuffix;
					//memoized.put(input, str);
					return str;
				}
			}
			memoized.put(input, null);
		}

		return null;
	}

	public void segment(String str) {
		List<String> strList = new LinkedList<String>();
		segmentHelp(str, 0, strList);
	}

	private void segmentHelp(String str, int current, List<String> words) {
		if (current == str.length()) {
			for (String s : words)
				System.out.printf("%s ", s);
			System.out.println();
			return;
		}

		for (int i = current + 1; i <= str.length(); ++i) {
			String prefix = str.substring(current, i);
			if (dictionary.contains(prefix)) {
				words.add(prefix);
				segmentHelp(str, i, words);
				words.remove(words.size() - 1);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//String str = "microsoftofficemicrosoftoffice";
		String str = "aaaab";
		// str = "abc";
		WordsExtractor we = new WordsExtractor();
		// we.segment(str);
		Map<String, String> memoized = new HashMap<String, String>();
		System.out.println(we.SegmentStringIterativeDP(str));
		System.out.println(we.SegmentStringRecusiveDP(str, memoized));
	}

}
